Date: Wed, 15 Jan 1997 00:10:44 GMT
Server: Apache/1.1.1
Content-type: text/html
Content-length: 3671
Last-modified: Fri, 05 Apr 1996 18:19:03 GMT

<!DOCTYPE HTML PUBLIC "-//W3O//DTD W3 HTML 2.0//EN">
<!Converted with LaTeX2HTML 95 (Thu Jan 19 1995) by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds >
<HEAD>
<TITLE> Algebraic Specification of Interconnection Network
Relationships</TITLE>
</HEAD>
<BODY>
<meta name="description" value=" Algebraic Specification of Interconnection Network
Relationships">
<meta name="keywords" value="main">
<meta name="resource-type" value="document">
<meta name="distribution" value="global">
<P>
 <BR> <HR><!WA0><A NAME=tex2html337 HREF="http://www.cs.columbia.edu/info/research-guide/html/node23.html"><!WA1><IMG ALIGN=BOTTOM ALT="next" SRC="http://www.cs.columbia.edu/info/research-guide/html/icons//next_motif.gif"></A>   <!WA2><A NAME=tex2html335 HREF="http://www.cs.columbia.edu/info/research-guide/html/node21.html"><!WA3><IMG ALIGN=BOTTOM ALT="up" SRC="http://www.cs.columbia.edu/info/research-guide/html/icons//up_motif.gif"></A>   <!WA4><A NAME=tex2html329 HREF="http://www.cs.columbia.edu/info/research-guide/html/node21.html"><!WA5><IMG ALIGN=BOTTOM ALT="previous" SRC="http://www.cs.columbia.edu/info/research-guide/html/icons//previous_motif.gif"></A>   <!WA6><A NAME=tex2html339 HREF="http://www.cs.columbia.edu/info/research-guide/html/node1.html"><!WA7><IMG ALIGN=BOTTOM ALT="contents" SRC="http://www.cs.columbia.edu/info/research-guide/html/icons//contents_motif.gif"></A>      <BR>
<B> Next:</B> <!WA8><A NAME=tex2html338 HREF="http://www.cs.columbia.edu/info/research-guide/html/node23.html"> Algebraic Specification of </A>
<B>Up:</B> <!WA9><A NAME=tex2html336 HREF="http://www.cs.columbia.edu/info/research-guide/html/node21.html"> Jonathan L. Gross</A>
<B> Previous:</B> <!WA10><A NAME=tex2html330 HREF="http://www.cs.columbia.edu/info/research-guide/html/node21.html"> Jonathan L. Gross</A>
<BR> <HR> <P>
<H2><A NAME=SECTION000101000000000000000> Algebraic Specification of Interconnection Network
Relationships</A></H2>
<P>
When a distributed algorithm is designed for one parallel architecture (the
``guest'') and it is to be executed on another (the ``host''), the two
architectures are modeled as interconnection networks, and the guest is
mapped into the host.  Trees, meshes, and hypercubes are readily specified
and mapped by undergraduate-level mathematical methods.  Hypercube
variations, such as cube-connected-cycle graphs, wrapped butterfly graphs,
shuffle-exchange graphs, and deBruijn graphs are specified as Cayley graphs
and group-action graphs (``GAG's'') for wreath products of cyclic groups.
(See Rosenberg [Ro90] and Leighton [Le92].)
<P>
The <i> voltage graph</i> construction (see Gross and Tucker [GrTu87]), which
is my combinatorial abstraction of a Riemann surface, was originally
introduced in order to simplify the specification of networks and their
layouts on surfaces.  More recently, my work has been concerned with
extending the algebraic specification of the networks to the representation
of guest-host relationships between two networks, by modeling it as a
voltage graph morphism, that is, as a mapping from one voltage graph to
another.
<P>
For one example of an application, my topological techniques and algebraic
formulas for measuring load, congestion, and dilation of guest-host
relationships readily reduce the representation of a cube-connected cycle
network into a wrapped butterfly network to specifying a graph function
from a circular ladder to a doubled cycle.  For another, these techniques
and formulas reduce the representation of a shuffle exchange network in a
deBruijn network to specifying a graph function from the bouquet
<!WA11><IMG  ALIGN=MIDDLE ALT="" SRC="http://www.cs.columbia.edu/info/research-guide/html/img5.gif"> to itself.  The <i> bouquet</i> <!WA12><IMG  ALIGN=MIDDLE ALT="" SRC="http://www.cs.columbia.edu/info/research-guide/html/img6.gif"> is defined to
be the graph with one vertex and <b>n</b> self-loops.
<P>
I am presently working on voltage graph morphism lifting in collaboration
with Jianer Chen (of Texas A&amp;M).  David Seidman (of IBM and EE Dept.) has
also begun work with me on this topic.
<P>
<P>
<P>
<BR> <HR>
<P><ADDRESS>
<I>Sabah S. al-Binali <BR>
Fri Sep 22 16:39:42 EDT 1995</I>
</ADDRESS>
</BODY>
